package com.future;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * Description: 253. 会议室 II
 *
 * @author weiruibai.vendor
 * Date: 2022/7/5 14:37
 */
public class Solution_253 {

    public static void main(String[] args) {

        int[][] intervals = new int[][]{
                {0, 30}, {5, 10}, {15, 20}
        };
        intervals = new int[][]{
                {7, 10}, {2, 4}
        };

        intervals = new int[][]{
                {2, 10}, {4, 10}, {10, 20}, {10, 30}
        };
        System.out.println(minMeetingRooms(intervals));
    }

    public static int minMeetingRooms(int[][] intervals) {
        Comparator<Meeting> MY_COMPARATOR = (o1, o2) -> o1.start != o2.start ? o1.start - o2.start : o2.end - o1.end;
        Meeting[] meetings = new Meeting[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            meetings[i] = new Meeting(intervals[i][0], intervals[i][1]);
        }
        Arrays.sort(meetings, MY_COMPARATOR);
        int ans = 1;
        /**
         * 对于不同的开始时间有相同的结束时间
         * eg：{2, 10}, {4, 10}, {10, 20}, {10, 30}
         * 当安排了{2,10}、{4,10}，需要两个会议室,可以记录为
         * {
         *     {2,10}->null
         *     {4,10}->null
         * }
         * 当遍历到{10,20}时，可以安排如下
         * {
         *     {2,10}->{10,20}
         *     {4,10}->null
         * }
         * 或
         * {
         *     {2,10}->null
         *     {4,10}->{10,20}
         * }
         * 这时treeSet值应该为{10,20}
         * 当遍历到{10，30}时，就可以无缝衔接用，安排如下
         * {
         *     {2,10}->{10,20}
         *     {4,10}->{10,30}
         * }
         */
        Map<Integer, Integer> keyTimesMap = new HashMap<>();
        /**
         * treeSet存排好序的数据
         */
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < meetings.length; i++) {
            Meeting meeting = meetings[i];
            if (treeSet.isEmpty()) {
                // 第一次
                treeSet.add(meeting.end);
                keyTimesMap.put(meeting.end, 1);
                continue;
            }
            Integer preEnd = treeSet.floor(meeting.start);// 比start小的且最接近的！！
            if (preEnd == null) {
                ans++;
            } else {
                Integer times = keyTimesMap.get(preEnd);
                if (times == null || times == 1) {
                    keyTimesMap.remove(preEnd);
                    treeSet.remove(preEnd);
                } else {
                    keyTimesMap.put(preEnd, times - 1);
                }
            }
            treeSet.add(meeting.end);
            Integer times = keyTimesMap.get(meeting.end);
            keyTimesMap.put(meeting.end, times == null ? 1 : times + 1);
        }
        return ans;
    }

    private static class Meeting {
        public int start;
        public int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Meeting{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

}
